#include "quick_sort.h"
#include "utils.h"
#include "benchmark.h"

static int partition(int *split);

void quickSort(int *a, int start, int finish) {
	int i, split;
	if (start >= finish)
		return; 
	split = partition(a, start, finish);
	quickSort(a, start, split-1);
	quickSort(a, split+1, finish);
}

static int partition(int *a, int left, int right) {
	int pivot, l,r;
	pivot = a[left];
	l = left+1;
	r = right;

	while (TRUE) {
		while (benchAddOperation(benchmark) && l < r && a[r] >= pivot) r--;
		while (benchAddOperation(benchmark) && l < r && a[l] < pivot) l++;
		if (l == r)
			break;
		swap(a,l,r);
	}
	if (a[l] >= pivot)
		return left;
	a[left] = a[l];
	a[l] = pivot;

	return l;
}